There is a continuously growing demand for improved performance in communication systems in general and in wireless networks in particular. Multicasting is an approach for improving the throughput by efficiently transmitting the same information to multiple users/receivers. When the channel is unreliable, it may not be possible to deliver the data to all receivers in a reliable way. Therefore multicasting over unreliable channels typically requires the use of Forward Error Correction (FEC) techniques or backward error correction techniques such as Automatic Repeat reQuest (ARQ).
So-called Fountain coding is an interesting approach for reliable multicast [1-2]. Fountain coding is an ideal rate-less data encoding scheme, a form of FEC, which produces new parity information until all users have decoded the sent data file. Approximation of ideal fountain codes are so called Tornado codes and LT-codes. Other Fountain codes include so called Tornado codes and Online codes. The basic philosophy, in LT codes (and generally in most Fountain codes) in which new parity information is formed, is based on randomly selecting the coding degree, i.e. the number of packets to be coded together, according to a predefined degree distribution and then bitwise XORing (modulo 2 adding) the packets. While not inherently a part of the Fountain coding, an acknowledgement is typically sent when the receiver have received sufficient number of parity packets that enable decoding, and not earlier than that. Hence, only one acknowledgement is needed for a FC file per user. Those approximations of FC enable efficient multicasting in erasure channels where roughly an amount ε more redundancy than data needs to be received.
ARQ is an efficient error control strategy for data transmission where the receiver detects transmission errors in the messages and automatically requests retransmission from the sender. Usually feedback messages from the receivers to the sender are used to enable the sender to determine which packets have been received correctly by the intended receivers and which ones have not. The packets that have not been received correctly must be resent.
ARQ is proposed to be used as a standard for communication over the air interface in cellular wireless communication systems, and can also be used in multihop systems. Typically, the information is divided into smaller packets, called protocol data units (PDU), prior to the transmission. A reliable transfer is enabled by encoding packets with an error detecting code, such that the receiver can detect erroneous or lost packets and thereby request retransmission. The data sequence integrity is normally ensured by sequential numbering of packets and applying certain transmission rules.
It may be useful to first review the basic principles for ARQ based on unicast before discussing details on multicast ARQ, keeping in mind that the basic principles from unicast ARQ mostly carry over to multicast ARQ.
In the most simple form of ARQ, commonly referred to as Stop-and-Wait ARQ, the sender of data stores each sent data packet and waits for an acknowledgement from the receiver of a correctly received data packet, by the way of an acknowledgement message (ACK). When the ACK is received, the sender discards the stored packet and sends the next packet. The process is typically supplemented with timers and the use of negative acknowledgement messages (NACK). The sending entity uses a timer, which is started on the transmission of a data packet, and if no ACK (or NACK) has been received before the timer expires, the data packet is retransmitted. If the receiver detects errors in the packet, it can send a NACK to sender. Upon receiving the NACK, the sender retransmits the data packet without waiting for the timer to expire. If the ACK or NACK message is lost, the timer will eventually expire and the sender will retransmit the data packet.
From the simple Stop-and-Wait, more elaborated schemes of the conventional ARQ has been developed, for example Go-Back-N and Selective Reject (or Selective Repeat), which provides a higher throughput.
In another line of development of the ARQ, the redundancy in the coding is exploited in various ways to enhance communication performance (generally measured as throughput). These schemes are referred to as Hybrid ARQ schemes. A combination of coding and ARQ, the hybrid ARQ schemes, can give a certain adaptation to changes in the radio environment, e.g. to fading. In Hybrid 1 ARQ, FEC is combined with ARQ. In Hybrid 2 ARQ, a PDU is sent more or less FEC encoded, but accompanied with a Cyclic Redundancy Check (CRC) for checking presence of bit errors after decoding and if retransmission is requested, parity bits (also known as redundancy bits) generated by a FEC coder, systematic bits, or a combination of both is sent.
If efficiency is not the main target, multiple parallel unicast ARQ processes may be used to ensure reliable “multicast”. This may be a common approach when the size of the multicast group, i.e. the number of intended receivers, is small. For larger groups, this is however an inefficient way of communication. It is therefore typically considered more efficient to merge the parallel unicast processes into a single so-called multicast ARQ process, where the same information is transmitted to multiple users [3].
Reference [4] relates to optimization of the performance for reliable multiple unicast flows.
References [5-7] describe schemes where the same data is multicasted to multiple users, and efficient retransmission is enabled by combining several packets negatively acknowledged (NACKed) by different receivers into a single block.
A problem with traditional multicast ARQ in general is that the performance is extremely poor when the number of users is large. In fact, it is noted as well as easily realized that the throughput efficiency goes towards zero when the number of users K goes towards infinity.
While fountain coding alleviates the performance problems in traditional multicast ARQ, its performance is roughly T=p/(1+ε), where T is the throughput efficiency, ε depends on the amount of data being sent and p is the reception probability. In [2], it was roughly stated that 1+ε is more than 1.06 with probability 1/10 and was not more than 1.10 in 10 000 trials of a so-called Tornado Z code implementation. Moreover it is stated that Tornado codes do not have tight enough bounds on the decoding inefficiency for commercial applications, and that for current commercial Digital Fountain implementations of LT codes, the decoding inefficiency is more than 1.05 with probability less than 10 for almost any size source file.
There are several drawbacks with Fountain coding. FC relies on statistically ensuring decodability by over provisioning of redundancy information, and does not rely on deterministic decodability. First, one typically requires large amounts of information for a small value of ε and the performance is typically poor when only a small amount of data packets is communicated. The time to decode the delivered data is fairly long as all redundancy needs to be received before decodability can be guaranteed. LT codes, a form of Fountain codes, are also known to have a bad error floor behavior that at least in part have been addressed by other FC like Tornado codes.
Although the schemes proposed in references [5-7] represent a step in the right direction for multicast ARQ with deterministic decodability, these schemes do still not provide optimum performance. A reason for this is that traditional multicast ARQ operation is more static than needed and does not recognize and exploit all degrees of freedom.
There is thus a general need for an even more throughput-efficient strategy for reliable multicasting.